#!/usr/bin/lua


-----------------------------------------------------------
---                                                     ---
---    Simulador de autômatos estruturados com pilha    ---
---    Versão Linux                                     ---
---                                                     ---
-----------------------------------------------------------


--------------- Variáveis Globais ---------------

-- Indica se imprime informações de rastreamento
imprimeInfo = nil

-- Indica se a cadeia será lida do teclado
leTeclado = nil

-- Arquivo que contém a especificação
fileSpecs = nil

-- Arquivo que contém a cadeia
fileCadeia = nil

-- Tabela de estados e transições
transicoes = {}

-- Tabela que identifica os estados de aceitação da sub-máquina
aceitacao = {}

-- Tabela que contém os estados com chamadas de sub-máquina
chamadaSubMaquina = {}

-- Variável temporária que contém o número de estados de uma sub-máquina do autômato
numeroEstados = nil

-- Tabela que contém o estado inicial de cada sub-máquina do autômato
estadoInicial = {}

-- Variável que contém a sub-máquina atual do autômato
subMaquinaAtual = nil

-- Variável que contém o estado atual do autômato
estadoAtual = nil

-- Variável que contém o próximo estado da transição
estadoProximo = nil

-- Variável que contém o estado anterior após transição
estadoAnterior = nil

-- Pilha
pilha = {}
pilha.topo = nil
pilha.dado = {}


--------------- Fim de Variáveis Globais ---------------


--------------- Funções ---------------

-- Inicializa pilha
function pilha.inicializa ()

	pilha.topo = -1

	pilha.dado = {}

end


-- Insere na pilha
function pilha.insere (p)

	pilha.topo = pilha.topo + 1
	
	pilha.dado[pilha.topo] = p

end


-- Remove da pilha o elemento do topo
function pilha.remove ()

	pilha.topo = pilha.topo - 1

end


-- Retorna elemento do topo da pilha
function pilha.retornaTopo ()

	return pilha.dado[pilha.topo]

end


-- Verifica se pilha está vazia
function pilha.vazia ()

	if pilha.topo == -1 then
		return true
	
	else
		return false

	end

end


-- Função que adiciona o estado e suas transições à tabela de estados e transições
function adicionaEstado (subMaquina, baseTransicao)

	if imprimeInfo == true then
		print ("Sub-máquina: ", subMaquina)

		print ("Estado: ", baseTransicao)

		print ("Transições a partir deste estado:")

	end

	-- Cria entradas nas tabelas para o estado que está sendo lido do arquivo
	transicoes[subMaquina][baseTransicao] = {}
	chamadaSubMaquina[subMaquina][baseTransicao] = {}

	-- Marca, neste primeiro momento, o estado como não sendo de aceitação
	aceitacao[subMaquina][baseTransicao] = false
	
	-- Marca, neste primeiro momento, o estado como não sendo de chamada de sub-máquina
	chamadaSubMaquina[subMaquina][baseTransicao] = nil
	
	-- Cria uma tabela auxiliar com as transições do estado lido
	transicaoAux = {}

	charCount = 0

	-- Identifica no arquivo os símbolos
	for char in string.gmatch (currentLine, " . ") do
		char2Count = 0

		-- Loop para corrigir aquisição do símbolo
		-- Símbolo é adquirido como " K " ao invés de "K"
		for char2 in string.gmatch (char, ".") do
			char2Count = char2Count + 1

			if char2Count == 2 then
				char = char2

				break

			end

		end

		estadoCount = 0

		charCount = charCount + 1

		transicaoAux[char] = {}

		-- Identifica no arquivo o estado após a transição
		for estadoFinal in string.gmatch (currentLine, "(%w+);") do
			estadoCount = estadoCount + 1
	
			if (estadoCount == charCount) then
				transicaoAux[char] = estadoFinal

				if imprimeInfo == true then
					print (baseTransicao, char, transicaoAux[char])

				end

			end

		end

	end


	mCount = 0

	-- Identifica o nome da sub-máquina nas transições
	for maquina in string.gmatch (currentLine, "<.->") do
		estadoCount2 = 0

		mCount = mCount + 1

		transicaoAux[maquina] = {}


		-- Identifica no arquivo o estado após a transição
		for estadoFinal in string.gmatch (currentLine, "(%w+),") do
			estadoCount2 = estadoCount2 + 1

			if (estadoCount2 == mCount) then
				transicaoAux[maquina] = estadoFinal

				if imprimeInfo == true then
					print (baseTransicao, maquina, transicaoAux[maquina])

				end

			end

		end
		
		-- Marca o estado como chamada de sub-máquina
		chamadaSubMaquina[subMaquina][baseTransicao] = maquina
		
	end


	-- Inclui os símbolos e transições para o estado na tabela
	transicoes[subMaquina][baseTransicao] = transicaoAux
	
end


-- Função que verifica se o símbolo pertence ao alfabeto
function verificaSimbolo (simbolo)

	for char in string.gmatch (alfabeto, simbolo) do
		flag = true

		return true

	end

	return false

end


-- Função que lê o símbolo e efetua a transição de estados no autômato
function transicaoEstado (subMaquina, simbolo)

	--print ("pilha.vazia () == ", pilha.vazia ())

	-- Próximo estado
	estadoProximo = transicoes[subMaquina][estadoAtual][simbolo]

	if imprimeInfo == true and estadoProximo ~= nil then
		print (estadoAtual, simbolo, estadoProximo)

	end
	
	return estadoProximo

end


--------------- Fim de Funções ---------------


--------------- Main ---------------

print ("\n")

print ("Deseja imprimir informações para rastreamento? Digite 's' para sim ou 'n' para não e pressione Enter: ")

imprimeInfoAux = io.read ()

-- Troca o tipo do valor da variável de string para booleano
if imprimeInfoAux == "s" then
	imprimeInfo = true

else
	imprimeInfo = false

end


---------- Leitura do arquivo de especificação do autômato ----------

while fileSpecs == nil do

	print ("\n")

	print ("Digite o nome do arquivo que contém a especificação do autômato e pressione Enter.")

	print ("Se nenhum nome for especificado, será utilizado o arquivo 'automato.txt'")

	filename = io.read ()

	if filename == "" then
		fileSpecs = io.open ("automato.txt", "r")

	else
		fileSpecs = io.open (filename, "r")	

	end


	if fileSpecs == nil then
		print ("Arquivo não encontrado!")

		break

	end

end


----- Alfabeto -----

-- Lê do arquivo de entrada o alfabeto

alfabeto = fileSpecs:read ("*l")

if imprimeInfo == true then
	print ("\n")

	print ("Descrição do autômato")

	print ("\n")

	print ("Alfabeto: ", alfabeto)

end


----- Número de sub-máquinas -----

-- Lê do arquivo de entrada o número de sub-máquinas do autômato

numeroSubMaquinas = fileSpecs:read ("*l")

if imprimeInfo == true then
	print ("Número de sub-máquinas: ", numeroSubMaquinas)

end


for l = 1, numeroSubMaquinas do

	----- Nome da sub-máquina -----

	-- Lê do arquivo de entrada o nome da sub-máquina

	nomeSubMaquina = fileSpecs:read ("*l")
	
	print ("\n")

	if imprimeInfo == true then
		print ("Nome da sub-máquina: ", nomeSubMaquina)

	end

	-- Cria uma entrada na tabela para a sub-máquina que está sendo lida do arquivo
	transicoes[nomeSubMaquina] = {}

	-- Cria uma entrada na tabela de estados de aceitação para a sub-máquina que está sendo lida do arquivo
	aceitacao[nomeSubMaquina] = {}
	
	-- Cria uma entrada na tabela de estados de chamada de sub-máquina
	chamadaSubMaquina[nomeSubMaquina] = {}


	----- Número de estados -----

	-- Lê do arquivo de entrada o número de estados da sub-máquina

	numeroEstados = fileSpecs:read ("*l")

	if imprimeInfo == true then
		print ("Número de estados: ", numeroEstados)

	end


	----- Estado -----

	-- Adiciona os estados e transições do arquivo na tabela de transição de estados

	for k = 1, numeroEstados do
		currentLine = fileSpecs:read ("*l")

		if imprimeInfo == true then
			print ("\n")

		end

		for estado in string.gmatch (currentLine, "(%w+):") do
			adicionaEstado (nomeSubMaquina, estado)

		end
	
	end


	----- Estado Inicial -----

	-- Extrai do arquivo o estado inicial da sub-máquina

	estadoInicialAux = fileSpecs:read ("*l")

	-- Cria na tabela de estados iniciais a entrada para a sub-máquina atual
	estadoInicial[nomeSubMaquina] = {}

	estadoInicial[nomeSubMaquina] = estadoInicialAux

	if imprimeInfo == true then
		print ("\n")

		print ("Estado inicial: ", estadoInicial[nomeSubMaquina])

	end


	----- Estados de aceitação -----

	-- Extrai do arquivo os estados de aceitação da sub-máquina

	currentLine = fileSpecs:read ("*l")

	if imprimeInfo == true then
		print ("Estados de aceitação: ", currentLine)

	end

	for estado in string.gmatch (currentLine, "(%w+)") do
		aceitacao[nomeSubMaquina][estado] = true

	end

end


----- Sub-máquina principal -----

-- Lê do arquivo de entrada o nome da sub-máquina principal

subMaquinaPrincipal = fileSpecs:read ("*l")

print ("\n")

if imprimeInfo == true then
	print ("Sub-máquina principal: ", subMaquinaPrincipal)

end



---------- Fim de Leitura do arquivo de especificação do autômato ----------


---------- Leitura do arquivo que contém a cadeia de entrada ----------

while leTeclado == nil do

	print ("\n")

	print ("Deseja ler a cadeia a partir de um arquivo ou do teclado?")

	print ("Digite 'a' para ler de arquivo ou 't' para ler do teclado e pressione Enter")

	leTecladoAux = io.read ()

	-- Troca o tipo do valor da variável de string para booleano
	if leTecladoAux == "t" then
		leTeclado = true

	elseif leTecladoAux == "a" then
		leTeclado = false

	end


	if leTeclado == false then

		print ("\n")

		print ("Digite o nome do arquivo que contém a cadeia de entrada e pressione Enter.")

		print ("Se nenhum nome for especificado, será utilizado o arquivo 'cadeia.txt'")

		filename = io.read ()

		if filename == "" then
			fileCadeia = io.open ("cadeia.txt", "r")

		else
			fileCadeia = io.open (filename, "r")	

		end

		if fileCadeia == nil then
			print ("Arquivo não encontrado!")

			break

		end

	end

end


---------- Fim de Leitura do arquivo que contém a cadeia de entrada ----------


---------- Transição de estados ----------

-- Lê do arquivo ou teclado a cadeia de entrada
if leTeclado == false then
	cadeia = fileCadeia:read ("*l")

elseif leTeclado == true then
	print ("\n")

	print ("Digite a cadeia de entrada e pressione Enter: ")

	cadeia = io.read ()

end


-- Posiciona o autômato em seu estado inicial
subMaquinaAtual = subMaquinaPrincipal
estadoAtual = estadoInicial[subMaquinaAtual]
estadoAnterior = estadoAtual

-- Inicializa a pilha
pilha.inicializa ()

if imprimeInfo == true then
	print ("\n")

	print ("Cadeia: ", cadeia)

	print ("\n")
	
	print ("Sub-máquina: ", subMaquinaAtual)

	print ("\n")

	print ("Estado inicial: ", estadoAtual)

	print ("\n")

	print ("Transições:")

end


-- Executa a função de transição de estados para cada símbolo da cadeia
for simbolo in string.gmatch (cadeia, ".") do
	simboloAux = simbolo

	existeSimbolo = nil
	
	-- Detectar parênteses, colchetes e chaves tendem a gerar erros no interpretador Lua
	-- Nesses casos, coloca-se um "%" na frente do caractere
	if simbolo == "(" then
		simboloAux = "%("
	
	elseif simbolo == ")" then
		simboloAux = "%)"

	elseif simbolo == "[" then
		simboloAux = "%["

	elseif simbolo == "]" then
		simboloAux = "%]"

	elseif simbolo == "{" then
		simboloAux = "%{"

	elseif simbolo == "}" then
		simboloAux = "%}"

	end

	-- Verifica se o símbolo pertence ao alfabeto
	existeSimbolo = verificaSimbolo (simboloAux)
	
	--print ("existeSimbolo == ", existeSimbolo)
	
	-- Sai do loop caso o símbolo não pertença ao alfabeto
	if existeSimbolo ~= true then
		if imprimeInfo == true then
			print (estadoAtual, simbolo)
			print ("Símbolo inexistente no alfabeto: ", simbolo)

		end

		estadoAtual = nil

		break

	elseif existeSimbolo == true then
	
		-- Se estado não faz chamada de sub-máquina
		if chamadaSubMaquina[subMaquinaAtual][estadoAtual] == nil then
			estadoAtual = transicaoEstado (subMaquinaAtual, simbolo)
			
			-- Se não existe transição, deve terminar a chamada da sub-máquina			
			if estadoAtual == nil then
			
				-- Verifica se o estado final da chamada é de aceitação
				if aceitacao[subMaquinaAtual][estadoAnterior] == true then
					print ("Retorno da sub-máquina ", subMaquinaAtual)
				
					-- Volta para o estado anterior à chamada
					estadoAtual = pilha.dado[pilha.topo].estado
					
					-- Efetua transição de estados, considerando fim da chamada
					estadoAtual = transicaoEstado (pilha.dado[pilha.topo].subMaquina, subMaquinaAtual)
					
					-- Volta para a sub-máquina anterior à chamada
					subMaquinaAtual = pilha.dado[pilha.topo].subMaquina
					
					-- Efetua a transição de estados para o símbolo lido
					estadoAtual = transicaoEstado (subMaquinaAtual, simbolo)
					
					-- Desempilha configurações
					pilha.remove ()
					
				end
					
			end

		-- Se estado faz chamada de sub-máquina
		elseif chamadaSubMaquina[subMaquinaAtual][estadoAtual] ~= nil then
			pilhaAux = {}

			pilhaAux.subMaquina = subMaquinaAtual
			pilhaAux.estado = estadoAtual

			-- Empilha configurações
			pilha.insere (pilhaAux)
			
			-- Faz a chamada de sub-máquina
			subMaquinaAtual = chamadaSubMaquina[subMaquinaAtual][estadoAtual]

			-- Posiciona no estado inicial da sub-máquina
			estadoAtual = estadoInicial[subMaquinaAtual]

			print ("Chamada de sub-máquina ", subMaquinaAtual)

			-- Efetua a transição de estados
			estadoAtual = transicaoEstado (subMaquinaAtual, simbolo)
			
		end

	end
	
	if estadoAtual == nil then
		if imprimeInfo == true then
			print (estadoAnterior, simbolo)
		
			print ("Transição inexistente")
				
		end
		
		break

	end
	
	estadoAnterior = estadoAtual
	
end

print ("\n")


-- Verifica se o estado é de aceitação
if aceitacao[subMaquinaAtual][estadoAtual] == true then
	print ("Cadeia aceita")

elseif aceitacao[subMaquinaAtual][estadoAtual] == false and estadoAtual ~= nil then
	print ("Estado não é de aceitação")

	print ("Cadeia rejeitada")

else
	print ("Transição e/ou símbolo inexistente(s)")

	print ("Cadeia rejeitada")

end

print ("\n")


---------- Fim de Transição de estados ----------

print ("Pressione Enter para encerrar")

encerra = io.read ()


--------------- Fim de Main ---------------


--------------- Fim do arquivo ---------------

